1. Field of the Invention
The present invention relates to table searching techniques and in particular to a table searching system and method for use in, for example, a database system or a switching system such as a packet switching system or a router.
2. Description of the Related Art
In a packet communication network, typically the Internet, packet transmission from a source to a destination is performed by packet switches such as routers, each of which forwards a received packet to a next hop node based on the destination address of the packet. Recently, in addition to the packet routing operation, the need may arise for a router to handle additional processing for IPsec (IP Security). IPsec is a security protocol working at layer 3 and is expected to become the standard for virtual private networks (VPNs) on the Internet. Therefore, the need for a high-speed router is growing and several techniques have been proposed.
The inventor has proposed an improved packet switch in Japanese Patent Application No. 11-098140 filed on Apr. 5, 1999 (Unexamined Publication No. P2000-295274A published on Oct. 20, 2000). The proposed packet switch uses a table searching hardware device to allow a burden upon a microprocessor to be reduced, resulting in increased routing and IPsec processing speed.
More specifically, the packet switch is provided with an IP flow table registering a routing result obtained by the routing process using the source and destination addresses of an IP packet as a search key. When receiving an IP packet, the IP flow table is searched using the IP source and destination addresses of the received packet as a search key. When a hit is found in the IP flow table, the microprocessor performs a forwarding operation of the packet based on the found routing result information without performing the routing process. Similarly, by performing IPsec processing with a security processor as hardware, the packet switching with security processing can be performed at high speeds.
In routing and IPsec processing, recently, handling new IP (Internet Protocol) traffic of encapsulated packets or Aggregated flow has been required of a router. Aggregated flow includes a plurality of IP packets to be transferred to the same destination router. More specifically, these IP packets are aggregated by an encapsulating header whose routing information is determined based on the IP destination and source addresses of the included packets. In this case, an IP traffic of original IP packets is called Micro flow.
The proposed packet switch as described above can achieve the simplified device configuration and the high-speed switching by performing the forwarding processing of original packets (Micro flow) and encapsulated packets (Aggregated flow) with the same hardware.
In the case where the processing procedure for aggregated IP traffic is changed due to, for example, invalidation of security association, however, update of the table searching hardware device cannot be completed rapidly. More specifically, since entries in the IP flow table are created in the order in which IP traffic appeared, the microprocessor searches the IP flow table for entries related to the aggregated IP traffic and, when a hit is found, the microprocessor can update the found entry depending on a change of the aggregated IP traffic.
Such a search process as described above is performed for all the entries in the IP flow table. Therefore, in the case of a large number of entries, the time required for the search is not negligible. Further, during the search, the primary search operation for switching cannot be performed. Accordingly, the search speed of the packet switch is reduced and thereby the packet switch throughput is also lowered.
One method for solving such a problem may be considered such that the address of entry for each IP flow (micro flow) is directly stored in a database including a routing table. But it is not preferable. In general, it is not determined how many micro flows belong to a single aggregated flow. Therefore, it is difficult to estimate the size of database and therefore an vacancy may be generated in the ensured database area.
The same problem may occur in not only a router but also any searching system. For example, consider that a searching system having a dedicated search table in addition to a database is designed to store data that has been searched for into the dedicated search table. In such a searching system, when the search is started, the dedicated search table is first searched and, if no hit is found in the dedicated search table, then the database is searched. In order to ensure high-speed searching, the capacity of the dedicated search table should be limited. Accordingly, if there is data with low use frequency or data after the expiration of a preset time interval, then the data should be deleted from the dedicated search table in the order of registration.
Especially, in the case where a plurality of pieces of data are associated with each other, it is not easy to be consistent with the database. When a chain of pieces of data is deleted from the database, the related data should be deleted from the dedicated search table. At this time, it is necessary to search the dedicated search table for all related data. Therefore, high-speed searching and updating operation cannot be achieved.